package com.javabasic.algorithm.leetcode;

/**
 * @Author xiongmin
 * @Description
 * @Date 2021-04-07 22:44
 * @Version 1.0
 **/
public class BestTimeToBuyAndSellStock {

    public int maxProfit(int[] prices) {
        if (null == prices || prices.length == 1) {
            return 0;
        }
        int len = prices.length;
        int[] minNums = new int[len];
        int tag = 0;

        for (int price : prices) {
            if (tag == 0) {
                minNums[tag++] = prices[0];
            } else if (price < minNums[tag-1]) {
                minNums[tag++] = price;
            } else {
                minNums[tag] = minNums[tag-1];
                tag++;
            }
        }
        tag = 0;
        int result = 0;
        for (int price : prices) {
            if (price - minNums[tag] > result) {
                result = price - minNums[tag];
            }
            tag++;
        }
        return result;
    }


    /**
     * 算法优化：动态规划
     * dp数组表示的是，dp[index] 0-index子数组中最小的数
     * 前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}
     * @param prices
     * @return
     */
    public int maxProfit2(int[] prices) {
        if (null == prices || prices.length == 1) {
            return 0;
        }
        int len = prices.length;
        int[] dp = new int[len];
        int result = 0;
        dp[0] = prices[0];
        for (int i = 1; i < len; i++) {
            if (prices[i]-dp[i-1] > result) {
                result = prices[i]-dp[i-1];
            }
            if (prices[i] < dp[i-1]) {
                dp[i] = prices[i];
            } else {
                dp[i] = dp[i-1];
            }
        }
        return result;
    }
}
